GATE CSE 2016 SET-1
Q51.
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increasedby the same value ,then which of the following statements is/are TRUE? P: Minimum spanning tree of G does not change Q: Shortest path between any pair of vertices does not changeQ52.
Consider the weighted undirected graph with 4 vertices,where the weigh to edge {i, j} is given by the entry Wij in the matrix W. W=\begin{bmatrix} 0 & 2&8 & 5\\ 2& 0& 5 &8 \\ 8 & 5 & 0& x\\ 5&8 & x&0 \end{bmatrix} The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is ____.Q53.
Which one of the following is NOT a part of the ACID properties of database transactions?Q54.
Consider the following two phase locking protocol. Suppose a transaction T accesses (for read or write operations), a certain set of objects {O1,... ,Ok}. This is done in the following manner: Step 1. T acquires exclusive locks to O1,...,Ok in increasing order of their addresses. Step 2. The required operations are performed. Step 3. All locks are released. This protocol willQ55.
For a host machine that uses the token bucket algorithm for congestion control, the token bucket has a capacity of 1 megabyte and the maximum output rate is 20 megabytes per second. Tokens arrive at a rate to sustain output at a rate of 10megabytes per second. The token bucket is currently full and the machine needs to send 12megabytes of data. The minimum time required to transmit the data is _____seconds.Q56.
We want to design a synchronous counter that counts these quence 0-1-0-2-0-3 and then repeats. The minimum number of J-K flip flop srequired to implement this counteris ________.Q57.
Which of the following decision problems are undecidable? I. Given NFAs N1 and N2, is L(N1)\capL(N2) = \phi? II. Given a CFG G = (N,\Sigma ,P,S) and a string x \in\Sigma ^*, does x \in L(G)? III. Given CFGs G1 and G2, is L(G1) = L(G2)? IV. Given a TM M, is L(M) = \phi?